package com.bclz.al.linlist

import com.bclz.al.linlist.Practive.Node

import scala.annotation.tailrec

object Practive {


  def main(args: Array[String]): Unit = {
//    val unit = Node(4,Node(5,Node(10,null)))
//    deleteNodeInLinkedList(unit,1)
//    val value = reverseLinkedListViaTailRec(unit)
//    val value = reverseLinkedList(unit)
//    println(value)
    //1-2-3-4-5
    //1-2-3-5
    //1-3-5
    //3-5
    //5
    println(josephusProblem(5,1,0,2))
  }

  case class Node[T](var ele:T,var next:Node[T])

  /**
    * delete-node-in-a-linked-list
    * https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
    *
    * @param node
    * @param value
    */
  def deleteNodeInLinkedList(node:Node[Int],value: Int): Unit ={

      var lastNode=Node[Int](null.asInstanceOf[Int],node)
      var state=true
      while (lastNode.next!=null && state ){
        val currentVal=lastNode.next
        if(currentVal.ele==value){
          lastNode.next=currentVal.next
          state=false
        }else{
          lastNode=currentVal
        }

      }


  }

  /**
    *  https://leetcode-cn.com/problems/reverse-linked-list/
    *  reverse-linked-list
    */
  def reverseLinkedListViaTailRec(node:Node[Int]): Node[Int] ={
      @tailrec
      def rec(node:Node[Int],node2:Node[Int]): Node[Int] ={
          if(node.next==null){
            node.next=node2
            return node
          }
          rec(node.next,Node(node.ele,node2))
      }

     rec(node,null)
  }

  def reverseLinkedList(node:Node[Int]): Node[Int] ={

      var resultNode:Node[Int]=null
      var currentNode=node
      while(currentNode!=null){
        resultNode=Node(currentNode.ele,resultNode)
        currentNode=currentNode.next
      }
      resultNode
  }

  /**
    *  https://leetcode-cn.com/problems/linked-list-cycle/
    *  linked-list-cycle
    */
  def linkedListCycle(node:Node[Int]): Boolean ={
      //1.set存储之前所有的node,判断是否存在,时间复杂度o(n),空间复杂度o(n)
      //2.快慢指针法空间复杂度O(1),时间复杂度O(n)
      var slow  = node
      var fast  = node
      while(fast!=null||fast.next!=null){
        fast=fast.next.next
        slow=slow.next
        if(fast==slow || fast.next==slow){
          return true
       }
      }
      false
  }

  /**
    * 约瑟夫问题
    *
    * 人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。
    * 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
    *
    * 问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。
    * 1. 双链表按顺时针或者逆时针轮询，复杂度: n+s+m*n=O(m*n)
    * 2.
    * @param n 人数
    * @param s 开始位置
    * @param d 方向 0:正向,1:反向
    * @param m 跳过人数
    * @return
    */
  def josephusProblem(n:Int,s:Int,d:Int,m:Int):Int={
      class Node[T](var ele:T,var next:Node[T],var previous:Node[T]){}
      def generateLinkedListCircle(num:Int): Node[Int] ={
          val first:Node[Int]=new Node[Int](1,null,null)
          var current:Node[Int]=first
          for(i <- (0 until num-1)){
            val node=new Node[Int](i+2,null,current)
            current.next=node
            current=node
          }
          first.previous=current
          current.next=first
          first
      }
      if(s>n){
        throw new ArrayIndexOutOfBoundsException()
      }
      val circle = generateLinkedListCircle(n)
      var startPerson:Node[Int]=new Node[Int](null.asInstanceOf[Int],circle,null)
      for(_ <- (0 to s-1)){
        startPerson=startPerson.next
      }
      var skipAfterPerson:Node[Int]=startPerson
      while(skipAfterPerson.next!=skipAfterPerson){
        for(_ <- (0 until m)){
          if(d==0){
            skipAfterPerson=skipAfterPerson.next
          }else{
            skipAfterPerson=skipAfterPerson.previous
          }
        }
        skipAfterPerson=skipAfterPerson.next
        val previous = skipAfterPerson.previous
        val next = skipAfterPerson.next
        previous.next=next
        next.previous=previous
        skipAfterPerson=previous
      }
      skipAfterPerson.ele

  }

}
